科目名 △離散数学Ⅲ−A
担当教員   朝廣 雄一     
対象学年   2年   クラス   [162]  
講義室   12106教室   開講学期   前期  
曜日・時限   水1   単位区分   選必  
授業形態     単位数   2  
準備事項    
備考    

講義概要/Class Outline

情報科学の基礎として重要なグラフ理論について学ぶ。グラフ構造は様々な場面に出現し、特に情報科学や情報技術を学ぶ場合には、グラフの概念やそれに関わる諸問題や解決法を理解しておくことが重要である。グラフ構造の例としては、例えば、コンピュータネットワークの論理的な構造、カーナビゲーションシステムなどの情報機器で用いられる各種の地図の構造などが代表的なものである。本講義では、グラフの基礎的な概念ならびに各種のグラフの性質、さらにそれらに関わる諸問題について解説する。しっかりとした理解をするためには問題演習が有効であるので、講義形式のみではなく問題演習も適宜行いながら講義を進める。  

講義計画 /Class Structure

内容
1 講義概要
講義概要と計画を説明する。
2 グラフ構造の応用
色々な場面で出現するグラフ構造について、情報科学の観点から紹介する。
3 グラフの表現(集合)
計算機で扱う対象は記号あるいは数値を用いて符号化する必要がある。集合の概念を用いてグラフを符号化する方法について解説する。
4 グラフの表現(行列)
行列の概念を用いてグラフを符号化する方法について扱う。具体的には、隣接行列と接続行列について解説する。
5 次数
次数の概念ならびに関連するグラフの性質について解説する。
6 部分グラフ
部分グラフの概念について解説する。
7 小テスト1
第6回までの内容についてテストを行う。

8 グラフの同型
2つのグラフが同型であるという概念について解説する。
9 道と閉路
グラフ中に存在する道と閉路の概念と、関連して距離と直径について解説する。
10 オイラー道
特殊な構造を持つ道である、オイラー道について解説する。
11 平面グラフ
平面グラフの概念と彩色について解説する。
12
特殊なグラフ構造である木について解説する。
13 小テスト2
第8回から第12回の内容についてテストを行う。
14 補足と復習
補足と復習を行う。
 

学習・教育目標/Class Target 1. グラフ理論についての基礎的な事項を理解している。
2. グラフ理論についての基礎的な事項に関する問題を解くことができる。
3. グラフに関する特殊な性質を理解している。
4. グラフに関する特殊な性質に関する問題を解くことができる。  
評価基準/GradingCriteria 学習・教育目標の項目についての総合的な満足度を評価し、次のとおりとする。 秀:90%以上、優:80%以上、良:70%以上、可:60%以上、不可:60%未満  
評価方法/GradingMethod 小テスト、定期試験を総合して評価する。それぞれの配分については次のとおりとする。 小テスト 20%、定期試験80%  
受講上の注意/Class Rules 離散数学Iの内容の一部を用いるので、それらを理解していないと本講義の理解も困難な場合があることを承知した上で受講すること。  
受講制限/Prerequisit  
関連する科目/Related Class 離散数学(I,Ⅱ,III-B, Ⅳ-A, IV-B)、データ構造とアルゴリズム(I,Ⅱ, III)、計画数学、情報回路  
教科書/Text
著者名 牛島和夫 編著、相利民、朝廣雄一著  
著書名 離散数学  
出版社名 コロナ社  
ISBNコード  
指定図書/Assigned Books
著者名 Seymour Libshutz  
著書名 マグロウヒル大学演習 離散数学  
出版社名 オーム社  
ISBNコード  
著者名 柴田正憲、浅田由良  
著書名 情報科学のための離散数学  
出版社名 コロナ社  
ISBNコード  
参考文献/Bibliography
著者名 守屋悦朗  
著書名 コンピュータサイエンスのための離散数学  
>出版社名 サイエンス社  
ISBNコード